import random
import time  

class Sorter(object):
    '''快速排序.

    Attributes:
        l: 要排序的列表
    '''

    def __init__(self, l:list):
        self.__l = l

    def sort(self):
        self.__sort(self.__l, 0, len(self.__l) - 1)

    def __sort(self, l:list, start:int, end:int):
        if end <= start:
            return
        else:
            j = self.__part(l, start, end)
            self.__sort(l, start, j - 1)
            self.__sort(l, j + 1, end)

    def __part(self, l:list, start:int, end: int):
        '''把数组分成两个子数组，前一个数组里所有元素小于等于所有第二个数组里的元素

        Args:
            l: 待分割的数组
            start: 数组起始位置
            end: 数组结束位置
        
        Returns:
            j: 分割数组的位置
        '''
        i = start
        j = end
        while j > i:
            while l[i] <= l[start] and i < end:
                i += 1
            while l[j] >= l[start] and j > start:
                j -= 1
            if j > i:
                l[j], l[i] = l[i], l[j]
        l[j], l[start] = l[start], l[j]
        return j

if __name__ == "__main__":
    l = [random.randint(0,50000) for _ in range(50000)]
    #l = [3,2,5,7,3,9,1]
    sorter = Sorter(l)

    before = time.time()
    sorter.sort()
    after = time.time()
    print(after - before)  